package com.cskaoyan.com.mylist;

import java.util.Objects;

/**
 * 实现一个线性表:
 *
 * ​		实现一个Java类型(自己写的集合类), 它作为一个数据容器存在, 逻辑上表现为线性表
 *
 *  集合类(三个看待的角度):
 *      数据容器: 存储数据
 *      物理结构: 单向链表
 *      逻辑结构: 线性表
 *
 */
public class MyLinkedList {

    // MyLinkedList真正来存储数据的是一个单向链表
    private Node head; // MyLinkedList底层持有链表的头结点
    private int size; // 用来记录我们的MyLinkedList中存储了多少数据

    // 在使用者角度, MyLinkedList是一个数据容器,
    // 那么MyLinkedList就应该具有增删改查数据的方法
//        myLinkedList.add("zs");
//        myLinkedList.remove("zs");
//        myLinkedList.contains("zs");
//        myLinkedList.set("zs", "ls");

    /**
     * MyLinkedList的根据内容的添加方法
     * @param str: 要添加的内容
     * @return: 添加是否成功
     */
    public boolean add(String str){
        // 特殊情况: 判断链表是否为空
        if (isEmpty()){
            // 链表为空, 新添加的内容, 就是头也是尾
            head = new Node(str);
            size++;
            return true;
        }

        // 由于没有指明添加位置, 一般添加到尾部
        // 逻辑: 1,从头向后找到尾的位置, 2, 添加到尾部之后,作为新的尾结点

        Node mid = head; // 定义一个临时遍历结点
        // mid.next != null 说明,遍历结点的下一个结点存在, 向后遍历
        while (mid.next != null){
            mid = mid.next;
        }

        // mid就是原链表的尾结点, 把新添加的值, 作为新的尾结点
        // Node node = new Node(str);
        // mid.next = node;
        mid.next = new Node(str);
        size++;
        return true;
    }

    /**
     * MyLinkedList根据内容的删除方法
     * @param str: 要删除的内容
     * @return: 删除是否成功
     */
    public boolean remove(String str){
        // TODO: 边界条件
        //  删除: 不存在, 头, 中间, 尾
        //  步骤: 1, 先查找这个要删除的内容, 2, 找到了之后才能删除

        // 链表是否为空
        if (isEmpty()){
             return false;
            // throw new RuntimeException("list is empty");
        }

        // 先判断删除的是否是头结点
        // Objects工具类, 在这用来解决结点中的value可能是null的问题
        //     (a == b) || (a != null && a.equals(b));
        // Arrays.sort
        if (Objects.equals(str, head.value)){
        // if (str.equals(head.value)){
            // 删除的就是头结点
            head = head.next;
            size--;
            return true;
        }

        // 接下来删除的必然是中间或者尾结点: 先去找(找要删除结点的前一个)
        Node mid = head; // 定义的当前遍历结点前一个 (mid.next是要遍历的结点)

        // mid的下一个结点存在, 并且mid的下一个结点存储的内容也不是要查找的值
        //     ---> 标记结点要向后移动/向后遍历
        while (mid.next != null &&  !Objects.equals(str, mid.next.value)){
            mid = mid.next; // 向后遍历
        }

        // 上述循环有两个跳出条件
        // mid.next == null --> 没有存贮这个值
        // mid.next.value.equals(str) -->  找到了要删除的内容, mid.next结点存储的

        if (mid.next == null){
            // 说明mid遍历到尾部, 都没有找到要删除的内容
            // 说明这个链表中根本没有存储过这个数据
            return false;
        }

        // 找到了要删出的结点: mid的下一个结点
        // mid就是要删除结点的前一个结点
        mid.next = mid.next.next;
        size--;

        return true;
    }

    /**
     * MyLinkedList中, 根据内容的查找方法
     * @param str:  要查找的内容
     * @return: 是否存在
     */
    public boolean contains(String str){
        // 判断链表是否为空
        if (isEmpty()){
            return false;
        }
        // 链表不空, 查找某个内容, 仅仅需要遍历
        Node mid = head; // 定义一个遍历结点

        // mid这个遍历结点存在, 并且这个结点内部存储的并不是我想要的值
        //  --> 向后接着遍历
        while (mid != null && !Objects.equals(str, mid.value)){
            mid = mid.next;
        }


        // 上述循环两个结束条件
        // 1, mid == null --> 链表中没有存储这个值
        if (mid == null){
            return false;
        }
        // 2,Objects.equals(str, mid.value) 比较结果为真, 找到了mid结点存储要找的内容
        return true;
    }

    /**
     * MyLinkedList的根据内容的修改方法
     * @param oldValue: 被修改的旧值
     * @param newValue: 用来替换的新值
     * @return:  修改是否成功
     */
    public boolean set(String oldValue, String newValue){
        // 链表为空
        if (isEmpty()){
            return false;
        }

        // 遍历, 找到这个要修改的旧值
        Node mid = head; // 定义的遍历结点
        while (mid != null && !Objects.equals(oldValue, mid.value)){
            mid = mid.next;
        }
        // 没找到
        if (mid == null){
            return false;
        }
        // 找到了
        mid.value = newValue;

        return true;
    }


    // 同时我们希望MyLinkedList这个数据容器, 从逻辑上表现是个线性表
    // 怎么表现为一个线性表? 线性表中的数据是一个接着一个排列
    // 这也就意味着, 每一个在线性表这种逻辑中存在的数据, 都是有固定下标位置的
    // 所以怎么让一个集合类/数据容器,从逻辑上表现为一个线性表? 提供根据下标操作的方法(增删改查)
//        myLinkedList.add(0, "zs");
//        myLinkedList.remove(0);
//        myLinkedList.get(0);
//        myLinkedList.set(0, "ls");

    /**
     * MyLinkedList作为线性表的根据下标的添加方法
     * @param index: 要添加的下标位置
     * @param str: 要添加的内容
     * @return: 添加是否成功
     */
    public boolean add(int index, String str){
        // 判断下标是否合法
        if (index < 0 || index > size){
            throw new IllegalArgumentException("paramer is Illegal");
        }

        // 添加是头位置
        if (index == 0){
            // Node node = new Node(str);
            // node.next = head;
            // head = node;
            // 等价于
            head = new Node(str, head);
            size++;

            return true;
        }

        // 添加到尾部
        if (index == size){
            return add(str);
        }

        // 添加到中间位置 , 根据下标确定
        int tag = 1; // 下标标记
        Node mid = head; // 根据下标标记后移的链表结点位置标记

        while (tag !=  index){
            mid = mid.next;
            tag++;
        }

        // 上述循环走完, mid就是根据下标查找到的要添加位置之前的位置结点
        Node node = new Node(str);
        node.next = mid.next;
        mid.next = node;
        // 可以简写为: mid.next = new Node(str, mid.next);
        size++;

        return true;
    }

    /**
     * MyLinkedList作为线性表的根据下标的删除方法
     * @param index: 要删除的下标位置
     * @return: 被删除的内容
     */
    public String remove(int index){
        // 判断下标是否合法
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("paramer is Illegal");
        }

        // 先处理头位置的删除
        if (index == 0){
            // 如果确定要删除的是头结点, 先保存一下头结点存储的内容
            String value = head.value; // 保存被删除值
            head = head.next; // 头标记后移
            size--;
            return value;
        }

        // 走到这: 要么删除的是中间结点, 要么是尾结点
        //  先找到再说: 根据下标找
        Node mid = head;
        int tag = 1;

        while (tag != index){
            mid = mid.next;
            tag++;
        }
        // mid是要查找下标位置的: 前一个
        //  mid.next就是要删除的结点

        // 保存一下旧值
        String value = mid.next.value;

        // 删除mid.next
        mid.next = mid.next.next;
        size--;

        return value;
    }

    /**
     * MyLinkedList作为线性表的根据下标的查找方法
     * @param index: 要查找的下标位置
     * @return: 这个下标位置存储的内容
     */
    public String get(int index){
        // 判断下标是否合法
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("paramer is Illegal");
        }

        // 根据下标查找
        Node mid = head;
        int tag = 0;

        while (tag != index){
            mid = mid.next;
            tag++;
        }

        return mid.value;
    }

    /**
     * MyLikedList的根据下标的修改方法
     * @param index: 要修改的下标位置
     * @param newValue: 用来替换的新值
     * @return: 被替换的旧值
     */
    public String set(int index, String newValue){
        // 判断下标是否合法
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("paramer is Illegal");
        }

        // 根据下标查找
        Node mid = head;
        int tag = 0;

        while (tag != index){
            mid = mid.next;
            tag++;
        }
        // mid就是要查找的下标位置

        // 保存旧值
        String value = mid.value;
        // 新值覆盖
        mid.value = newValue;

        return value;
    }



    public Object[] toArray(){
        // 1, 创建一个数组: size
        Object[] objects = new Object[size];
        // 2, 把链表中数组, 复制到这个数组
        Node mid = head;
        for (int i = 0; i < size; i++) {
            objects[i] = mid.value;
            mid = mid.next;
        }
        return objects;
    }



    /**
     * 判断MyLinkedList是否为空(这个数据容器是否存储的有数据)
     * @return 是否有数据
     */
    public boolean isEmpty(){
        return size == 0;
    }
    /**
     * MyLinkedList存储的数据量
     * @return: 存储的数据个数
     */
    public int size(){
        return size;
    }

    class Node{
        String value;
        Node next;
        public Node(String value) {
            this.value = value;
        }

        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
